1. Field of the Invention
This invention relates to an adaptive maximum likelihood sequence estimator, used as an equalizer for compensating for distortions on a transmission channel, and constituted of a channel estimator and a Viterbi algorithm processor.
2. Description of Related Art
Digital mobile communications is currently in a period of rapid development In a land mobile communication, distortions on transmission channels need to be compensated by an equalizer, because frequency selective fading may occur due to many interference waves accompanied by delays and due to high speed movements of mobile terminals and may thereby grossly impair received signal waveforms. As a method applied to such an equalizer, a maximum likelihood sequence estimation method is known. The maximum likelihood sequence estimation method is one of the most effective equalizing methods for estimating the correct transmitting symbol sequence from the received signal waveforms which are distorted due to delay characteristics of the transmission channel, as of such frequency selective fading.
Referring to FIGS. 1 to 3, an outline of digital mobile communications is described as follows. In a digital mobile communication system, the time division multiple access (TDMA) method is used to effectively utilize a limited frequency band and to readily connect to the ISDN (Integrated Service Digital Network) service implemented in fixed communication networks.
FIG. 1 shows an example of a frame constitution for the TDMA method. In FIG. 1, one frame is composed of six time-slots Slot1 to Slot6. One or two time-slots are assigned to one user of the system. Each of the time-slots from Slot1 to Slot 6 is constituted of a 28-bit training sequence SYNC for training synchronizers and equalizers, a 12-bit information sequence SACCH for control a 12-bit sequence CDVCC for identifying adjacent channels, 260 bits of data formed on two 103-bit data sequences DATA, and a 12-bit reserved region RSVD.
FIG. 2 shows a block diagram of a transmitting and receiving system of a digital mobile communication handling such a TDMA frame. In this transmitting and receiving system, a receiver 30 is connected to the output of a transmitter 10 through a transmission channel 20. The transmitter 10 includes an encoder 11, a transmission low pass filter (LPF) 12, a modulator 13 and the like. The receiver 30 includes a demodulator 31, a receiving low pass filter (LPF) 32, an equalizer 33, a decoder 34, and the like.
In the transmitter 10, the encoder 11 converts input data b.sub.m (bit sequences in accordance with the TDMA frame constitution) into transmission symbol x.sub.n, and the transmission low pass filter 12 produces complex transmission base band signals s(t)by limiting the band of the transmission symbol x.sub.n. The modulator 13 modulates the complex transmission base band signals s(t) with a carrier and transmits them as signals sc(t) to the transmission channel 20.
The transmission signals s.sub.c (t) are affected with characteristics of the transmission channel 20, and the affected signals r.sub.c (t) reach the receiver 30. In the receiver 30, the demodulator 31 converts the signals r.sub.c (t) into complex base band signals r(t), which are band-limited by passing through the receiving low pass filter 32 and thereby become received complex base band signals y(t). These signals y(t) are sampled with a symbol interval T and given to the equalizer 33. The equalizer 33 compensates, based on the sampled values y.sub.n of the received signals y(t), the characteristics of the transmission channel 20 due to frequency selective fading, and estimates transmission symbol sequences. Finally, the decoder 34 decodes estimated values EX.sub.n (here, E represents estimation.) of the transmission symbols to obtain transmitted data Eb.sub.m.
The .pi./4-shift differential quadraphase shift keying (DQPSK) method can be used as a modulation method for the encoder 11. In the .pi./4 shift DQPSK method, binary data sequences b.sub.m composed of 0 and 1 are divided by every two bits, and one of phase differentials -3.pi./4, -.pi./4, .pi./4, 3.pi./4 is selectively assigned in conjunction with the two bits' combination taking one of the four possible features. Where the assigned phase differential is .DELTA..PHI..sub.n (n=1, 2, . . .) and where the absolute phase of the transmission symbol at time n is .PHI..sub.n, the absolute phase .PHI..sub.n of the transmission symbol at time n is sought according to a formula (1), and transmission symbols x.sub.n at the time n are yielded by converting, in accordance with a formula (2), the absolute phase .PHI..sub.n. EQU .PHI..sub.n =.PHI..sub.n-1 +.DELTA..PHI..sub.n ( 1) EQU x.sub.n =e.sup.j.PHI.n ( 2)
The input data b.sub.m are thus converted to a point (coded alphabet: any of 0 to 7) on a signal-space diagram (coded alphabet diagram) in FIG. 3, as a descriptive diagram of the .pi./4 shift DQPSK method. In FIG. 3, white circles represent transmission symbols in odd numbers, and hatched circles represent transmission symbols in even numbers. A phase shift between the time n and the time n+1 becomes any one of -3.pi./4, -.pi./4, .pi./4, and 3.pi./4. That is, if the time proceeds to the next, the symbol at the next time proceeds from the white circle to any black circle and from the black circle to any white circle.
As described above, many equalizers 33, in which the sampled values y.sub.n 's sequences Y={y1, y2, . . . , yN} corresponding to transmission symbols x.sub.n according to such a .pi./4 shift DQPSK method are given to compensate characteristics of the transmission channel 20 due to the frequency selective fading, are made according to the maximum likelihood sequence estimation method.
A maximum likelihood sequence estimation method described in "Digital Communications," authored by John. G. Proakis, published by McGraw-Hill, in 1983, pp. 548 to 627 is as follows. The maximum likelihood sequence estimation method is for estimating most probable (Likelihood) transmission symbol sequences X={x1, x2, . . . , xN} to realize sampled value sequences Y of received signals while the impulse response h(t) of the transmission channel 20 is known (or, in many situations, is adaptively renewed as described below) when the received signal sequences Y={y.sup.1, y.sup.2, . . . , y.sup.N } are obtained in a finite duration. The maximum likelihood sequence estimate is obtained by seeking, among 2.sup.N sequences composed of N symbols, the sequences {x.sup.1, x.sup.2, . . . , x.sup.N } which make an inverse-square of the distance between the sequence and the sampled value sequences Y shown in a formula (3) the largest (accordingly, or making the square of the distance the least). EQU .SIGMA..vertline.y.sup.k -.SIGMA.x.sub.m h(t-mT).vertline..sup.2( 3)
(wherein k is 1 to N; m is a variant indicating time for the sequences; the former .SIGMA. is for k=1 to N; the latter .SIGMA. is for all m affecting sampled values y.sup.k at time k.)
However, the Viterbi algorithm, well-known as a decoding method for convolutional codes, is applied in order to estimate the most likely transmission symbol sequences X, because it is in fact difficult to compute the formula (3) for all the possible 2.sup.N sequences and because the formula (3) contains convolutional operations.
Referring to FIG. 4, which shows a model of the transmission channel 20 in FIG. 2 described above, a principle of the Viterbi algorithm for the maximum likelihood sequence estimate is briefly described. The transmission channel 20 is assumed as a discrete-time channel model, shown in FIG. 4, in which the impulse response is finite. That is, the model of the transmission channel 20 is supposedly constituted of a successive stage of delay devices 40 for delaying only for symbol intervals T, a group of multipliers 41 for multiplying L+1 symbol sequence portions x.sub.n-0, x.sub.n-1, . . . , x.sub.n-L, each of which is different from one another by the symbol interval T corresponding to the length L.multidot.T of the impulse response derived from the successive stage, by impulse response components (hereinafter called tap coefficients) h.sub.0, h.sub.1, . . . , h.sub.L corresponding to the time, an accumulator 42 for achieving the summation of each multiplier's output, and an adder 43 for adding noise w.sub.n of the transmission channel 20 (additive white gaussian noise) to the output of the accumulator. The tap coefficients h.sub.m (m=0, . . . , L) are sampled values h(t-jT), which are sampled at the symbol interval T of the impulse response h(t) of the transmission channel 20 including transmitting and receiving low pass filters 12, 32 in FIG. 2.
Where the characteristics of the transmission channel 20 is thus supposed, the above formula (3) is represented by the following formula (4). EQU -.SIGMA..vertline.y.sup.k -.SIGMA.x.sub.k-p .multidot.h.sub.p.sup..vertline.2 ( 4)
(Wherein k is 1 to N; p is 0 to L; the former .SIGMA. is for k=1 to N; the latter .SIGMA. is for p=0 to L.)
In this formula (4), the summation J.sub.n up to time k=n can be represented by a formula (5) below using the summation J.sub.n-1 up to the time k=n-1. Here, J.sub.n is an amount in proportion to logarithmic probability of the received signal sequences from k=1 to k=n and is called a path metric. The second term in the right side of the formula (5) is an amount proportional to the logarithmic probability of the state transition described below and is called a branch metric. The summation .SIGMA.x.sub.n-p h.sub.p in the second term in the right side of the equation of the formula (5) is called a branch value specially in this specification. EQU J.sub.n =J.sub.n-1 -.vertline.y.sub.n -.SIGMA.x.sub.n-p h.sub.p.sup..vertline.2 ( 5)
Although this formula (5) shows that a value up to an intermediate time can be computed at every arrival of the sampled values y.sub.n of the received signals with respect to estimated values shown in the formula (3) of 2.sup.N symbol sequences that the transmission symbol sequence possibly takes, it is no less than a computation of all of 2.sup.N estimated values (path metrics).
In contrast, the Viterbi algorithm, as the sampled values proceed, converges symbol sequences, which is estimated as the transmission symbols from the 2.sup.N symbol sequences that the transmission symbol sequence possibly takes, using the estimated values (path metrics) up to the intermediate time, and reduces the amount of the computation. Hereinafter, the convergence will be described.
Since the state of the transmission channel's model as shown in FIG. 4 is by a partial sequence {x.sub.n-1, x.sub.n-2, . . . , x.sub.n-L-1 } of the transmission symbol sequences X, the state at time n-1 is expressed by state vector S.sub.n-1 shown in the formula (6). Accordingly, in the .pi./4 shift DQPSK method, 4.sup.L ways of the transmission channels are possible at a certain time. EQU S.sub.n-1 ={x.sub.n-1, x.sub.n-2, . . . , x.sub.n-L-1 } (6)
On the other hand, if a transition from state S.sub.n-1 at time n-1 to state S.sub.n at time n is considered, the manner of the transition can be four kinds that the symbol x.sub.n can take, because each of the partial sequence {x.sub.n-1, x.sub.n-2, . . . , x.sub.n-L-1 } for the state S.sub.n-1 and the partial sequence {x.sub.n, x.sub.n-1, . . . , x.sub.n-L } has the symbol x.sub.n as a vector component. Accordingly, a four-way transition from the state S.sub.n-1 with respect to each of 4.sup.L of state S.sub.n.
FIG. 5 is a trellis diagram showing such transitions of transmission channel state in conjunction with time. FIG. 5 shows a diagram according to the .pi./4 shift DQPSK method wherein the L is 1. In FIG. 5, the number of each state at the respective time represents the number of the transmission symbol shown in FIG. 3. The state transition between times is called as a branch, and the route between the states is called a path.
As described above, with respect to each of four possible states at time n in FIG. 5, there are paths (branches) from four states at the just previous time n-1. The Viterbi algorithm computes, at every time n, path metrics J.sub.n in conjunction with four possible paths of each state, according to the formula (5) described above using the path metrics J.sub.n-1 up to the just previous time, and selects the largest path. This computation remains four branches between successive times, and therefore remains 4.sup.L way paths at every time, thereby gradually converging past paths into one path. The estimated values Ex of the transmission symbol sequences X are obtained from a finally converged single path.
An example of constitution shown in FIG. 7 is known as a conventional maximum likelihood sequence estimator (equalizer 33) for achieving the estimated values Ex of the transmission symbol sequences X thus using the Viterbi algorithm. This maximum likelihood sequence estimator is constituted of a Viterbi algorithm processor 50 and a channel estimator 60. The Viterbi algorithm processor 50 is constituted of a branch metric computer 51, an ACS (Add-Compare-Select) portion 52, a path metric memory 53, and a path history memory 54.
The sampled values y.sub.n of received signals are fed to the Viterbi algorithm processor 50 and the channel estimator 60. In the channel estimator 60, the impulse response of the transmission channel is estimated by an adaptive algorithm such as LMS (Least Mean Square) or the like using training sequences (SYNC in FIG. 1) and the sampled values y.sub.n of received singles corresponding to them. After this computation, the channel estimator 60 continues to estimate the impulse response of the transmission channel using the sampled values y.sub.n of received singles and the estimated value EXn of the transmission symbol. The estimated tap coefficients Eh.sub.p (p=0, . . . , L: hereinafter, represented simply by h.sub.p), which are the impulse response components of the transmission channel, are fed to the Viterbi algorithm processor 50.
In the Viterbi algorithm processor 50, the branch metric computer 51 computes the branch metrics in the second term of the formula (5) from the sampled values y.sub.n of received singles and the tap coefficients Eh.sub.p supplied from the channel estimator 50. The ACS portion 52 obtains surviving paths and their path metrics from the branch metrics and the path metrics J.sub.n up to the time right before (in the first term of the formula (5)) and supplies the surviving paths to the path history memory 54 and the path metrics J.sub.n to the path metric memory 53. The path metric memory 53 supplies the path metrics J.sub.n-1 to the ACS portion 52. The path history memory 54 supplies a converged surviving path if the surviving paths are converged into one.
The Viterbi algorithm processor 50 thus estimates the transmission symbol sequences X in accordance with the principle described above from the sampled values y.sub.n of received signals and the estimated tap coefficients h.sub.p. It is to be noted that, since the impulse response of the transmission channel is adaptively changed, the maximum likelihood estimator shown in FIG. 7 is deemed as an adaptive maximum likelihood sequence estimator.
In general, intersymbol distances are used for the path metrics J.sub.n as of the estimated values for estimating the transmission symbol sequence X, and in the case that the transmission channel's model is the white gaussian transmission channel the Euclidean distance (including its square) has been frequently used as in the described formula (5).
If such path metrics J.sub.n are computed according to the defining formula, however, the computation becomes a larger amount. If the transmission symbol sequences X are estimated in use of software, the processing period of time becomes longer, whereas if the transmission symbol sequences X are estimated in use of hardware, the constitution becomes complex and the processing period becomes longer. For example, if the modulation method is the .pi./4 shift DQPSK method, the path metric J.sub.n is sought by the formula (5), but it takes so much time to compute the values of the branch metrics corresponding to the second term of the right side of the formula (5) as turned out from the formula (5). In the case of the .pi./4 shift DQPSK method, the value of the symbols and the impulse response components are complex, so that the operations are more complicated than seen from the formula (5). Similarly, such problems of the operation amount may happen in the case that, as a matter of course, the transmission symbols are estimated in accordance with other modulation methods.